package 链表系列;

import java.util.HashSet;
import java.util.Set;

public class DetectCycle {
    public ListNode detectCycle(ListNode head){
        //双指针法
        ListNode fast = head;   //快指针
        ListNode slow = head;   //慢指针
        while (fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast){   //有环
                ListNode index1 = fast;
                ListNode index2 = head;
                //两个指针，从头节点和相遇节点，各走一步，知道相遇，相遇点即为环入口
                while (index1 != index2){
                    //具体原因见 https://programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html#%E5%88%A4%E6%96%AD%E9%93%BE%E8%A1%A8%E6%98%AF%E5%90%A6%E6%9C%89%E7%8E%AF
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1;
            }
        }

        return null;
    }

    //哈希表法
//    public ListNode detectCycle(ListNode head) {
//        ListNode pos = head;
//        Set<ListNode> visited = new HashSet<ListNode>();
//        while (pos != null) {
//            if (visited.contains(pos)) {
//                return pos;
//            } else {
//                visited.add(pos);
//            }
//            pos = pos.next;
//        }
//        return null;
//    }

}
